Step 3: Formatting the Output

The algorithm is done! Now we just need to collect the results and print them in the required format.

Guidance for Step 3

  • Total Cost: The `key` array now holds the cost of the edge that brought each planet into the MST. The sum of all values in `key` is the total minimum cost.
  • Build Edge List: Create an empty list `mst_edges`. Loop from `i = 1` to `N-1` (we skip `0` because it's the root).
  • Standardize Edge: For each `i`, the edge is `(parent[i], i)`. To match the output format, make sure the smaller ID is first. If `parent[i] > i`, set `u, v = i, parent[i]`.
  • Sort Edges: Sort the `mst_edges` list. Python's default `sort()` will work perfectly, sorting by the first element (`u`), and then by the second (`v`) if there's a tie.
  • Print: Print the `total_cost` formatted to 2 decimal places. Then, loop through your sorted `mst_edges` and print each `u` and `v`. 
# --- 3. Process and Print the Output ---

# The 'key' array now stores the cost of the edge that
# brought each planet into the MST.
total_cost = ____(key)

# The 'parent' array stores the tree structure.
# We build the list of (u, v) edges from it.
mst_edges = []
# Start at 1 (skip root Planet 0, it has no parent)
for i in range(____, N): 
    u = parent[i]
    v = i
    
    # Standardize: Ensure u <= v
    if u > v:
        u, v = v, u
        
    mst_edges.append( ____ )

# Sort: Sort by u, then by v (canonical order)
____.sort()

# --- Print the final results ---
# Line 1: Total cost, 2 decimal places
print(f"{total_cost:.2f}")

# Lines 2 to N: The N-1 edges
for u, v in mst_edges:
    print(f"{u} {v}")
Copied!